-
1 travelling salesman problem
задача о коммивояжере
задача о бродячем торговце
Вид задачи математического программирования, состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. В обобщенной форме задача формулируется как определение на сети такого пути, связывающего два или более узлов, который минимизирует (или максимизирует) некоторый критерий оптимальности, представляющий собой функцию (как правило, сумму) известных характеристик ребер этой сети. На допустимые маршруты могут быть наложены ограничения: например, запрет возвращения к уже пройденному узлу. З.о к. — одна из типичных задач, решаемых методом динамического программирования. О сложности ее говорит такой факт: если рассматриваются четыре города (точки), то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов. В общем случае, когда число городов n, количество маршрутов равно (n-1)!, т.е. «(n-1) факториал». Задача, следовательно, заключается в поиске сокращенных способов расчета, позволяющих отказаться от сплошного перебора возможных маршрутов. Такие способы есть. Они основаны на использовании сетевых и матричных моделей. Алгоритмы, позволяющие решать на компьютерах З.о к., используются не только для выбора оптимальных маршрутов автотранспорта при кольцевой доставке товаров (например, в торговую сеть), но и при решении таких задач, которые на первый взгляд никакого отношения к З.о.к. не имеют, например, в планировании производства на конвейерах, выпускающих машины различных моделей. С помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера.
[ http://slovar-lopatnikov.ru/]Тематики
Синонимы
EN
Англо-русский словарь нормативно-технической терминологии > travelling salesman problem
-
2 travelling salesman problem
French\ \ problème du voyageur de commerceGerman\ \ Rundfahrtproblem; Traveling-Salesman-ProblemDutch\ \ handelsreizigers-probleemItalian\ \ commesso problema di viaggioSpanish\ \ problema del viajanteCatalan\ \ problema del viatjantPortuguese\ \ problema do caixeiro-viajanteRomanian\ \ -Danish\ \ -Norwegian\ \ -Swedish\ \ -Greek\ \ πρόβλημα του ταξιδιώτη πωλητήFinnish\ \ kauppamatkustaja ongelmaHungarian\ \ utazó ügynök problémaTurkish\ \ gezgin satıcı problemiEstonian\ \ rändkaupmehe ülesanneLithuanian\ \ prekijo problema; keliaujančiojo prekijo problemaSlovenian\ \ -Polish\ \ problem komiwojażeraRussian\ \ проблема (задача) коммивояжераUkrainian\ \ задача комівояжераSerbian\ \ -Icelandic\ \ ferðast sölumaður vandamálEuskara\ \ -Farsi\ \ -Persian-Farsi\ \ مسئله فروشنده دورهگردArabic\ \ مسألة البائع المتجولAfrikaans\ \ handelsreisigerprobleemChinese\ \ ( 规 划 论 中 的 ) 旅 行 推 销 员 题Korean\ \ - -
3 travelling salesman problem
иссл. опер. = traveling salesman problemАнгло-русский экономический словарь > travelling salesman problem
-
4 travelling salesman problem
problem komiwojażeraEnglish-Polish dictionary for engineers > travelling salesman problem
-
5 travelling-salesman problem
GB < math> (Hamilton loop) ■ Rundfahrtproblem n ; Problem des Handlungsreisenden n ; Handlungsreisendenproblem nEnglish-german technical dictionary > travelling-salesman problem
-
6 travelling salesman problem
задача о коммивояжёре (NP-полная задача: по данному графу с целочисленными весами рёбер найти цикл, который включает каждый узел и сумма весов рёбер которого не превосходит k)Англо-русский словарь промышленной и научной лексики > travelling salesman problem
-
7 travelling salesman problem
Математика: задача коммивояжёра, задача о коммивояжёреУниверсальный англо-русский словарь > travelling salesman problem
-
8 travelling-salesman problem
Вычислительная техника: задача коммивояжёраУниверсальный англо-русский словарь > travelling-salesman problem
-
9 Travelling Salesman Problem
Mathematics: TSPУниверсальный русско-английский словарь > Travelling Salesman Problem
-
10 travelling salesman problem
• задача за търговския пътникEnglish-Bulgarian polytechnical dictionary > travelling salesman problem
-
11 travelling salesman problem
English-Russian dictionary of logistics > travelling salesman problem
-
12 travelling salesman problem
English-Russian scientific dictionary > travelling salesman problem
-
13 travelling-salesman problem
English-Russian information technology > travelling-salesman problem
-
14 travelling salesman problem: TSP
probleem van de handelsreizigerEnglish-Dutch technical dictionary > travelling salesman problem: TSP
-
15 traveling salesman problem
иссл. опер. задача коммивояжера, задача о коммивояжере, задача о бродячем торговце (задача, заключающаяся в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд)Syn:Англо-русский экономический словарь > traveling salesman problem
-
16 problem komiwojażera
• travelling salesman problem• vehicle routingSłownik polsko-angielski dla inżynierów > problem komiwojażera
-
17 Problem des Handlungsreisenden
n < math> (Streckenoptimierung; Hamiltonkreis) ■ traveling salesman problem (TSP) US ; travelling-salesman problem GB ; shortest-route problemGerman-english technical dictionary > Problem des Handlungsreisenden
-
18 problem
1) задача; проблема3) трудность, затруднение•- boundary value problem - card matching problem - central limit problem - decision problem under risk - decision problem under uncertainty - extremum problem - fair division problem - gambling problem - gasoline blending problem - incompletely structured problem - optimal path problem - optimal stopping problem - portfolio selection problem - precisely specified problem - recursively solvable problem - sequential decision programming problem - sequential occupancy problem - shortest path problem - shortest route problem - standard control problem - three houses and three wells problem -
19 traveling salesman
-
20 field salesman
См. также в других словарях:
Travelling Salesman Problem — [ trævəlɪȖ seɪlzmən prɔbləm, englisch], Problem des Handelsreisenden, Rundfahrtproblem, Operations Research: kombinatorisches Optimierungsproblem, bei dem durch eine vorgegebene Menge von Orten von einem bestimmten Ausgangsort aus der kürzeste… … Universal-Lexikon
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Travelling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
Travelling Salesman Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
travelling salesman problem — noun The problem in combinatorial optimization in which, given a number of cities and the costs of travelling from one to the other, it is required to determine the cheapest route that visits each city once and then returns to the initial city … Wiktionary
Travelling salesman (disambiguation) — A travelling salesman is a travelling vendor of goods.Travelling salesman may also refer to:* Traveling Saleseman (film), a 1921 comedy film * Traveling Salesmen ( The Office episode), the twelfth episode of the third season of the US version of… … Wikipedia
Bottleneck traveling salesman problem — The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph with the minimal weight of the most weighty edge of the… … Wikipedia
Function problem — In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.Notable examples include the travelling salesman problem, which asks for the … Wikipedia
P versus NP problem — Unsolved problems in computer science Is P = NP ? … Wikipedia
Job-shop problem — The job shop problem (JSP) is a problem in discrete or combinatorial optimization, and is a generalization of the famous travelling salesman problem. It is a prominent illustration of a class of problems in computational complexity theory which… … Wikipedia
P = NP problem — The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize… … Wikipedia